/**
 * 
 * 整体思路描述： 
 *  借助一个数组p, 存储每个位置元素之前的元素；
 * 借助result，存储遍历到i时，每个长度对应子串的末尾元素；
 * 构建完成之后，拿到result对应的最末尾元素，去数组p中查找前一个索引，直至将该序列元素全部找到，即得到相应的结果
 * 
 * @param {number[]} nums
 * @return {number[]}
 */
function getSequence(arr) {

    // 存储的是当前的子串，每个位置存储的是子串前一个值的索引，可通过最后一个元素，倒序遍历得到完整子串。存储的均为索引
    const p = []
    // 存储的是当前索引所代表长度的子串的末尾数值索引，比如 result[2] = 3 存储的是长度为2 的最长子串的末尾数值为3；
    // 另外一个重要的作用是，可以为下一个比较的元素，找到它所属的递增子串的前一个值（由二分查找获取），如果能找到，便能借此更新p中对应的值
    // 所以result 本身也是一个递增数组，但连起来形成的数值串，并无太多实际意义。
    const result = [0]
    let i, j, u, v, c
    const len = arr.length
    for (i = 0; i < len; i++) {

        const arrI = arr[i]
        // 第 i 个元素
        if (arrI !== 0) {
            // 当前结果末尾元素的index
            j = result[result.length - 1]
            // 如果第i个元素比当前结果末尾元素大（当前所遍历到的元素，与结果相比【注意这里不是跟前一个，是跟result】，满足递增的条件）
            if (arr[j] < arrI) {
                // p 的第i个位置的下标更新为 当前末尾的下标
                p[i] = j
                // 将i 存入到result中
                result.push(i)
                // 继续查找下一个元素
                continue
            }

            // 如果不满足递增趋势
            u = 0
            v = result.length - 1
            // 从 0 到 当前result 的最末尾索引，二分查找，找到result中最接近 arrI的index
            while (u < v) {
                // 相当于Math.floor((u+v)/2)
                c = (u + v) >> 1

                // 如果位于result[c] 的值  小于 arrI, 也就是说
                if (arr[result[c]] < arrI) {
                    u = c + 1
                } else {
                    v = c
                }
            }
            //  此时 先判断当前arrI是否比U位置的值小，如果不小于，可能是第一个元素，则不进行处理
            if (arrI < arr[result[u]]) {
                // 意味着存在 比 arrI小的值
                if (u > 0) {
                    // 说明，u-1位置是当前子序列的当前元素位置（i）的前一个，此时，更新p[i]的值
                    p[i] = result[u - 1] // result中存的是真实索引
                } else {
                    // 说明不存在，找到了新序列的第一个，第一个不需要存入p[i]
                }
                // 此时，新的子序列以位置u结尾，因此需要记录新的子序列末尾元素的索引，即i
                // 此时的U是以 arr[i]结尾的子序列的末尾
                result[u] = i
            }
        }
    }
    u = result.length
    v = result[u - 1]
    console.log(p)
    while (u-- > 0) {
        // 这里是真实的值
        result[u] = arr[v]
        // 这是返回的索引
        // result[u] = v
        v = p[v]
    }
    return result
}

// console.log(getSequence([1, 3, 5, 2, 4, 6, 12]))
// console.log(getSequence([4, 3, 5, 1, 8, 4, 12, 6]))
console.log(getSequence([3, 5, 4, 2]))
